import java.util.Arrays;

/**
 * 494. 目标和
 */
public class No494 {
    int[] nums;

    /**
     * 1.零一背包动态规划
     */
    public int findTargetSumWays1(int[] nums, int target) {
        target += Arrays.stream(nums).sum();
        if (target < 0 || target % 2 == 1) return 0;
        target /= 2;
        this.nums = nums;
        int length = nums.length;
        return dfs1(length - 1, target);
    }

    private int dfs1(int i, int c) {
        if (i < 0) return c == 0 ? 1 : 0;
        if (c < nums[i]) return dfs1(i - 1, c);
        return dfs1(i - 1, c) + dfs1(i - 1, c - nums[i]);
    }

    int[][] cache;

    /**
     * 1.1 记忆化搜索优化
     */
    public int findTargetSumWays2(int[] nums, int target) {
        target += Arrays.stream(nums).sum();
        if (target < 0 || target % 2 == 1) return 0;
        target /= 2;
        this.nums = nums;
        int length = nums.length;
        cache = new int[length][target + 1];
        for (int[] ints : cache) {
            Arrays.fill(ints, -1);
        }
        return dfs2(length - 1, target);
    }

    private int dfs2(int i, int c) {
        if (i < 0) return c == 0 ? 1 : 0;
        if (cache[i][c] != -1) return cache[i][c];
        if (c < nums[i]) cache[i][c] = dfs2(i - 1, c);
        else cache[i][c] = dfs2(i - 1, c) + dfs2(i - 1, c - nums[i]);
        return cache[i][c];
    }

    /**
     * 2.递推（改递归为循环）
     */
    public int findTargetSumWays3(int[] nums, int target) {
        target += Arrays.stream(nums).sum();
        if (target < 0 || target % 2 == 1) return 0;
        target /= 2;
        int length = nums.length;

        int[][] f = new int[length + 1][target + 1];
        f[0][0] = 1;
        for (int i = 0; i < length; i++) {
            for (int c = 0; c < target + 1; c++) {
                if (c < nums[i]) f[i + 1][c] = f[i][c];
                else f[i + 1][c] = f[i][c] + f[i][c - nums[i]];
            }
        }
        return f[length][target];
    }

    /**
     * 2.1 进阶，空间优化，两个滚动数组
     */
    public int findTargetSumWays4(int[] nums, int target) {
        target += Arrays.stream(nums).sum();
        if (target < 0 || target % 2 == 1) return 0;
        target /= 2;
        int length = nums.length;

        int[][] f = new int[2][target + 1];
        f[0][0] = 1;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < target + 1; j++) {
                if (j < nums[i]) f[(i + 1) % 2][j] = f[i % 2][j];
                else f[(i + 1) % 2][j] = f[i % 2][j] + f[i % 2][j - nums[i]];
            }
        }
        return f[length % 2][target];
    }

    /**
     * 2.2 进阶，空间优化，一个数组
     */
    public int findTargetSumWays5(int[] nums, int target) {
        target += Arrays.stream(nums).sum();
        if (target < 0 || target % 2 == 1) return 0;
        target /= 2;

        int[] f = new int[target + 1];
        f[0] = 1;
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                f[j] = f[j] + f[j - num];
            }
        }
        return f[target];
    }

}
